#include <iostream>
#include "Sort.h"
#include <vector>
#include <random>
#include <cstdlib>
#include <ctime>


using namespace std;

vector<int> order_vec(int n, double order)
{
    vector<int> a(n);
    for(int i=0; i<a.size(); i++)
        a[i] = i;
    int reorder_cal = 0;
    if (order*(n-1)/2 > 1)
    {
        while(reorder_cal < (1-order)*n*(n-1)/2)
        {
            random_device rd;
            mt19937 mt(rd());
            int i = (unsigned int)mt()%(unsigned int)n;
            if (a[n-i] == (n-i))
            {
                a[n-i] = 2*n - a[n-i];
                reorder_cal = reorder_cal + i;
            }
        }
    }
    else
    {
        while(reorder_cal < (1-order)*n*(n-1)/2)
        {
            random_device rd;
            mt19937 mt(rd());
            int i = (unsigned int)mt()%((unsigned int)order*n*(n-1)/2);
            if (a[n-i] == (n-i))
            {
                a[n-i] = 2*n - a[n-i];
                reorder_cal = reorder_cal + i;
            }
        }
    }
    return a;
}

double cal_order(vector<int> &a)
{
    int order_count = 0;
    for(int i=0; i<a.size(); i++)
    {
        for(int j=i+1; j<a.size(); j++)
        {
            if (a[i]<a[j])
                order_count++;
        }
    }
    return (double)order_count/(a.size()*(a.size()-1))*2;
}

void test_save2(double order, int n)
{
    double qk,qks,rev;
    double heap_aver=0, quick_aver=0, quicks_aver=0;
    vector<int> a(n);
    vector<int> heap,quick,quick_sf;
    clock_t start, stop;

    cout << "Degree of Order = "<< order << endl;
    rev = 0;
    for (int i=0; i<10; i++)
    {
        a = order_vec(n,order);
        heap = a;
        quick = a;
        quick_sf = a;
        cout << "The average saving time " << rev/CLOCKS_PER_SEC*1000 << "ms" << endl;
        start = clock();
        heapsort(heap);
        stop = clock();

        start = clock();
        quicksort(quick);
        stop = clock();
        qk = start - stop;
        quick_aver = quick_aver + (stop-start)/10;
        cout << "Quicksort using time: " << qk/CLOCKS_PER_SEC*1000 << "ms" << endl;

        start = clock();
        quicksort_sf(quick_sf);
        stop = clock();
        qks = start - stop;
        quicks_aver = quicks_aver + (stop-start)/10;
        cout << "Quicksort_sf using time: " << qks/CLOCKS_PER_SEC*1000 << "ms" << endl;

        rev = rev + (qk-qks)/10;
    }
    cout << "Quicksort averusing time: " << quick_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << "Quicksort_sf averusing time: " << quicks_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << "The average saving time " << rev/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << endl;
}

void test_save(double order, int n)
{
    double qk,qks,rev;
    double heap_aver=0, quick_aver=0, quicks_aver=0;
    vector<int> a(n);
    vector<int> heap,quick,quick_sf;
    clock_t start, stop;

    cout << "Degree of Order = " << order << endl;
    rev = 0;
    for (int i=0; i<10; i++)
    {
        a = order_vec(n,order);
        heap = a;
        quick = a;
        quick_sf = a;

        start = clock();
        heapsort(heap);
        stop = clock();
        heap_aver = heap_aver + (stop-start)/10;

        start = clock();
        quicksort(quick);
        stop = clock();
        qk = stop - start;
        quick_aver = quick_aver + (stop-start)/10;

        start = clock();
        quicksort_sf(quick_sf);
        stop = clock();
        qks = stop - start;
        quicks_aver = quicks_aver + (stop-start)/10;

        rev = rev + (qk-qks)/10;
    }
    cout << "Heapsort using time: " << heap_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << "Quicksort using time: " << quick_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << "Quicksort_sf using time: " << quicks_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << "The average saving time " << rev/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << endl;
}

void test(double order, int n)
{
    vector<int> a(n);
    vector<int> heap,quick;
    double heap_aver=0, quick_aver=0;
    clock_t start, stop;
    cout << "Degree of Order = " << order << endl;
    for (int i=0; i<10; i++)
    {
        a = order_vec(n,order);
        heap = a;
        quick = a;
        start = clock();
        heapsort(heap);
        stop = clock();
        heap_aver = heap_aver + (stop-start)/10;
        start = clock();
        quicksort(quick);
        stop = clock();
        quick_aver = quick_aver + (stop-start)/10;
    }
    cout << "Heapsort using time: " << heap_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << "Quicksort using time: " << quick_aver/CLOCKS_PER_SEC*1000 << "ms" << endl;
    cout << endl;
}

int main()
{
    int n = 50000;
    double order;
    clock_t start, stop;
    srand(time(0));

// // 有序度=0.99
//     order = 0.99;
//     test(order, n);

// // 有序度=0.9
//     order = 0.9;
//     test(order, n);

// // 有序度=0.5
//     order = 0.5;
//     test(order, n);

// // 有序度=0.1
//     order = 0.1;
//     test(order, n);

// // 有序度=0.01
//     order = 0.01;
//     test(order, n);

// 有序度=1
    order = 1;
    test_save(order, n);

    order = 0.99999;
    test_save(order, n);

    

    
    return 0;
}
